#include "fs/buf.h"
#include "fs/bitmap.h"
#include "fs/inode.h"
#include "fs/fs.h"
#include "mem/vmem.h"
#include "proc/cpu.h"
#include "lib/print.h"
#include "lib/str.h"

extern super_block_t sb;

// 内存中的inode资源 + 保护它的锁
#define N_INODE 32
static inode_t icache[N_INODE];
static spinlock_t lk_icache;

// icache初始化
void inode_init() {
    // 初始化全局锁，用于保护 inode 缓存的访问
    spinlock_init(&lk_icache, "icache");

    // 初始化 inode 缓存
    for (int i = 0; i < N_INODE; i++) {
        icache[i].inode_num = INODE_NUM_UNUSED;  // 将 inode 标记为未分配状态
        icache[i].ref = 0;                       // 引用计数设为 0
        icache[i].valid = false;                 // 初始时数据无效
        sleeplock_init(&icache[i].slk, "inode"); // 初始化 inode 的睡眠锁
    }
}

/*---------------------- 与inode本身相关 -------------------*/

// 使用磁盘里的inode更新内存里的inode (write = false)
// 或 使用内存里的inode更新磁盘里的inode (write = true)
// 调用者需要设置inode_num并持有睡眠锁
void inode_rw(inode_t* ip, bool write)
{   
    assert(ip->inode_num != INODE_NUM_UNUSED, "inode_rw: invalid inode_num");
    assert(sleeplock_holding(&ip->slk), "inode_rw: lock");

    //使用内存里的inode刷磁盘
    if (write)
    {
        buf_t* b = buf_read((ip->inode_num / INODE_PER_BLOCK) + sb.inode_start);

        inode_t *inode_in_ram = (inode_t *)b->data + (ip->inode_num % INODE_PER_BLOCK);
        inode_in_ram->type = ip->type;
        inode_in_ram->major = ip->major;
        inode_in_ram->minor = ip->minor;
        inode_in_ram->nlink = ip->nlink;
        inode_in_ram->size = ip->size;
        memmove(inode_in_ram->addrs, ip->addrs, sizeof(ip->addrs));
        buf_release(b);
    }
    else
    {
        buf_t* b = buf_read(ip->inode_num / INODE_PER_BLOCK + sb.inode_start);
        buf_release(b);
    }
}


// 在icache里查询inode
// 如果没有查询到则申请一个空闲inode
// 如果icache没有空闲inode则报错
// 注意: 获得的inode没有上锁
inode_t* inode_alloc(uint16 inode_num)
{
    inode_t* first_idle_inode = NULL; // 用于记录第一个空闲的 inode

    // 1. 加锁以保证对 icache 的互斥访问
    spinlock_acquire(&lk_icache);

    // 2. 检查是否有匹配的 inode_num
    for (int i = 0; i < N_INODE; i++) {
        inode_t* ip = &icache[i];
        if (ip->ref > 0 && ip->inode_num == inode_num) {
            ip->ref++; // 增加引用计数
            spinlock_release(&lk_icache);
            return ip; // 返回找到的 inode
        }
        // 记录第一个空闲 inode
        if (first_idle_inode == NULL && ip->ref == 0) {
            first_idle_inode = ip;
        }
    }

    // 3. 如果没有找到匹配的 inode，分配第一个空闲的 inode
    if (first_idle_inode) {
        first_idle_inode->inode_num = inode_num;
        first_idle_inode->ref = 1; // 初始化引用计数
        first_idle_inode->valid = false; // 初始设置为无效
        spinlock_release(&lk_icache);
        return first_idle_inode;
    }

    // 4. 如果没有空闲的 inode，抛出错误
    spinlock_release(&lk_icache);
    panic("inode_alloc: no free inode");
    return NULL; // 理论上不会到达这里
}

// 在磁盘里申请一个inode (操作bitmap, 返回inode_num)
// 向icache申请一个inode数据结构
// 填写内存里的inode并以此更新磁盘里的inode
// 注意: 获得的inode没有上锁
inode_t* inode_create(uint16 type, uint16 major, uint16 minor)
{
    // 1. 在磁盘上分配一个新的 inode 号
    uint16 inode_num = bitmap_alloc_inode();
    if (inode_num == (uint16)-1) {
        panic("inode_create: failed to allocate inode from bitmap");
        return NULL;
    }

    // 2. 在内存的 icache 中分配对应的 inode 结构
    inode_t* ip = inode_alloc(inode_num);
    if (ip == NULL) {
        panic("inode_create: inode_alloc failed");
        return NULL;
    }

    // 3. 锁住 inode，安全地初始化元数据
    inode_lock(ip);

    // 4. 初始化 inode 的元数据
    ip->type = type;
    ip->major = major;
    ip->minor = minor;
    ip->nlink = 1;  // 新创建的 inode 通常有 1 个链接
    ip->size = 0;
    memset(ip->addrs, 0, sizeof(ip->addrs));  // 清空地址块
    ip->valid = true;  // 表示内存中的 inode 数据已与磁盘同步

    // 5. 将 inode 的元数据写回磁盘
    inode_rw(ip, true);

    // 6. 解锁 inode
    inode_unlock(ip);

    // 7. 返回初始化后的 inode
    return ip;
}


// 供inode_free调用
// 在磁盘上删除一个inode及其管理的文件 (修改inode bitmap + block bitmap)
// 调用者需要持有lk_icache, 但不应该持有slk
static void inode_destroy(inode_t* ip)
{
    // 确保调用者不持有全局锁 lk_icache，但持有 inode 的睡眠锁
    assert(!spinlock_holding(&lk_icache), "inode_destroy: lk_icache must not be held");
    assert(sleeplock_holding(&ip->slk), "inode_destroy: inode lock must be held");

    // 释放 inode 管理的所有数据块，包括一级、二级和三级索引块
    for (int i = 0; i < N_ADDRS; i++) {
        if (ip->addrs[i] != 0) {
            if (i < N_ADDRS_1) {
                // 一级索引：直接释放数据块
                bitmap_free_block(ip->addrs[i]);
            } else if (i < N_ADDRS_1 + N_ADDRS_2) {
                // 二级索引：读取索引块，释放其中的数据块
                buf_t* b1 = buf_read(ip->addrs[i]);
                uint32* data1 = (uint32*)b1->data;
                for (int j = 0; j < ENTRY_PER_BLOCK; j++) {
                    if (data1[j] != 0) {
                        bitmap_free_block(data1[j]);
                    }
                }
                buf_release(b1);
                bitmap_free_block(ip->addrs[i]);
            } else {
                // 三级索引：读取第一级索引块
                buf_t* b1 = buf_read(ip->addrs[i]);
                uint32* data1 = (uint32*)b1->data;
                for (int j = 0; j < ENTRY_PER_BLOCK; j++) {
                    if (data1[j] != 0) {
                        // 读取第二级索引块
                        buf_t* b2 = buf_read(data1[j]);
                        uint32* data2 = (uint32*)b2->data;
                        for (int k = 0; k < ENTRY_PER_BLOCK; k++) {
                            if (data2[k] != 0) {
                                bitmap_free_block(data2[k]);
                            }
                        }
                        buf_release(b2);
                        bitmap_free_block(data1[j]);
                    }
                }
                buf_release(b1);
                bitmap_free_block(ip->addrs[i]);
            }
            ip->addrs[i] = 0; // 清空索引
        }
    }

    // 清空 inode 的元数据
    ip->type = FT_UNUSED;
    ip->major = 0;
    ip->minor = 0;
    ip->nlink = 0;
    ip->size = 0;

    // 写回磁盘，确保磁盘与内存一致
    inode_rw(ip, true);

    // 释放 inode 的 bitmap 标记
    bitmap_free_inode(ip->inode_num);

    // 标记为无效，表示该 inode 可重新分配
    ip->valid = false;
}

// 向icache里归还inode
// inode->ref--
// 调用者不应该持有slk
void inode_free(inode_t* ip)
{
    assert(ip->ref > 0, "inode_free: ref");
    if(ip->ref == 1)
    {
        inode_lock(ip);
        inode_destroy(ip);
        ip->type=FT_UNUSED;
        inode_rw(ip,true);
        ip->valid=0;
        inode_unlock(ip);
    }
    spinlock_acquire(&lk_icache);
    ip->ref--;
    spinlock_release(&lk_icache);

}

// ip->ref++ with lock
inode_t* inode_dup(inode_t* ip)
{
    spinlock_acquire(&lk_icache);
    ip->ref++;
    spinlock_release(&lk_icache);
    return ip;
}

// 给inode上锁
// 如果valid失效则从磁盘中读入
void inode_lock(inode_t* ip)
{
    if (ip == 0 || ip->ref < 1)
        panic("inode_lock");

    sleeplock_acquire(&ip->slk);
    if (ip->valid == 0)
    {
        inode_rw(ip, false);
        ip->valid = 1;
        assert(ip->type==FT_UNUSED||ip->type==FT_DIR||ip->type==FT_FILE||ip->type==FT_DEVICE,"unvalid type");
    }
}

// 给inode解锁
void inode_unlock(inode_t* ip)
{
    assert((ip == 0 || !sleeplock_holding(&ip->slk) || ip->ref < 1),"inode_unlock: invalid inode or not holding lock");
    sleeplock_release(&ip->slk);
}

// 连招: 解锁 + 释放
void inode_unlock_free(inode_t* ip)
{
    inode_unlock(ip);
    inode_free(ip);
}

/*---------------------------- 与inode管理的data相关 --------------------------*/

// 辅助 inode_locate_block
// 递归查询或创建block
uint32 locate_block(uint32* entry, uint32 bn, uint32 size)
{
    if(*entry == 0)
        *entry = bitmap_alloc_block();

    if(size == 1)
        return *entry;    

    uint32* next_entry;
    uint32 next_size = size / ENTRY_PER_BLOCK;
    uint32 next_bn = bn % next_size;
    uint32 ret = 0;

    buf_t* buf = buf_read(*entry);
    next_entry = (uint32*)(buf->data) + bn / next_size;
    ret = locate_block(next_entry, next_bn, next_size);
    buf_release(buf);

    return ret;
}

// 确定inode里第bn块data block的block_num
// 如果不存在第bn块data block则申请一个并返回它的block_num
// 由于inode->addrs的结构, 这个过程比较复杂, 需要单独处理
static uint32 inode_locate_block(inode_t* ip, uint32 bn)
{
    assert(sleeplock_holding(&ip->slk), "inode_locate_block: lock not held");
    assert(bn < N_ADDRS_1 + N_ADDRS_2 * ENTRY_PER_BLOCK + N_ADDRS_3 * ENTRY_PER_BLOCK * ENTRY_PER_BLOCK, "inode_locate_block: invalid block number");

    uint32 ret = 0;

    // 一级直接块
    if (bn < N_ADDRS_1) {
        ret = ip->addrs[bn];
        if (ret == 0) {
            ret = bitmap_alloc_block();
            assert(ret != 0, "inode_locate_block: bitmap_alloc_block failed");
            ip->addrs[bn] = ret;
            inode_rw(ip, true);
        }
    }
    // 二级间接块
    else if (bn < N_ADDRS_1 + N_ADDRS_2 * ENTRY_PER_BLOCK) {
        uint32 index = (bn - N_ADDRS_1) / ENTRY_PER_BLOCK + N_ADDRS_1;
        uint32 block_1 = ip->addrs[index];
        if (block_1 == 0) {
            block_1 = bitmap_alloc_block();
            assert(block_1 != 0, "inode_locate_block: bitmap_alloc_block failed");
            ip->addrs[index] = block_1;
            inode_rw(ip, true);
        }
        uint32 block_2 = (bn - N_ADDRS_1) % ENTRY_PER_BLOCK;
        buf_t* buf = buf_read(block_1);
        ret = *((uint32*)buf->data + block_2);
        if (ret == 0) {
            ret = bitmap_alloc_block();
            assert(ret != 0, "inode_locate_block: bitmap_alloc_block failed");
            *((uint32*)buf->data + block_2) = ret;
            buf_write(buf);
        }
        buf_release(buf);
    }
    // 三级间接块
    else if (bn < N_ADDRS_1 + N_ADDRS_2 * ENTRY_PER_BLOCK + N_ADDRS_3 * ENTRY_PER_BLOCK * ENTRY_PER_BLOCK) {
        uint32 index1 = (bn - N_ADDRS_1 - N_ADDRS_2 * ENTRY_PER_BLOCK) / (ENTRY_PER_BLOCK * ENTRY_PER_BLOCK) + N_ADDRS_1 + N_ADDRS_2;
        uint32 block_1 = ip->addrs[index1];
        if (block_1 == 0) {
            block_1 = bitmap_alloc_block();
            assert(block_1 != 0, "inode_locate_block: bitmap_alloc_block failed");
            ip->addrs[index1] = block_1;
            inode_rw(ip, true);
        }
        uint32 index2 = (bn - N_ADDRS_1 - N_ADDRS_2 * ENTRY_PER_BLOCK) / ENTRY_PER_BLOCK % ENTRY_PER_BLOCK;
        buf_t* buf_1 = buf_read(block_1);
        uint32 block_2 = *((uint32*)buf_1->data + index2);
        if (block_2 == 0) {
            block_2 = bitmap_alloc_block();
            assert(block_2 != 0, "inode_locate_block: bitmap_alloc_block failed");
            *((uint32*)buf_1->data + index2) = block_2;
            buf_write(buf_1);
        }
        buf_release(buf_1);
        uint32 index3 = (bn - N_ADDRS_1 - N_ADDRS_2 * ENTRY_PER_BLOCK) % ENTRY_PER_BLOCK;
        buf_t* buf_2 = buf_read(block_2);
        ret = *((uint32*)buf_2->data + index3);
        if (ret == 0) {
            ret = bitmap_alloc_block();
            assert(ret != 0, "inode_locate_block: bitmap_alloc_block failed");
            *((uint32*)buf_2->data + index3) = ret;
            buf_write(buf_2);
        }
        buf_release(buf_2);
    } else {
        panic("inode_locate_block: block number out of range");
    }

    return ret;
}

// 读取 inode 管理的 data block
// 调用者需要持有 inode 锁
// 成功返回读出的字节数, 失败返回0
uint32 inode_read_data(inode_t* ip, uint32 offset, uint32 len, void* dst, bool user)
{
    assert(sleeplock_holding(&ip->slk), "inode_read_data: lock not held");

    // 检查偏移量和长度是否合法
    if (offset > ip->size || offset + len < offset)
        panic("inode_read_data: invalid offset or length");
    
    // 调整读取长度为文件剩余部分
    if (offset + len > ip->size)
        len = ip->size - offset;

    uint32 n = 0;             // 已读取字节数
    uint32 bn = offset / BLOCK_SIZE; // 起始逻辑块号
    uint32 end_bn = (offset + len - 1) / BLOCK_SIZE; // 结束逻辑块号
    uint32 off = offset % BLOCK_SIZE; // 当前块内偏移量
    buf_t* buf;
    proc_t* p = myproc();
    pgtbl_t user_pgtbl = p->pgtbl;

    for (; bn <= end_bn; bn++) {
        // 根据逻辑块号找到对应的物理块号
        uint32 block_num = inode_locate_block(ip, bn);

        // 读取物理块数据
        buf = buf_read(block_num);

        // 计算本次读取的字节数
        uint32 copy_len = MIN(len - n, BLOCK_SIZE - off);

        // 根据用户态或内核态执行数据拷贝
        if (user) {
            uvm_copyout(user_pgtbl, (uint64)(dst + n), (uint64)(buf->data + off), copy_len);
        } else {
            memmove(dst + n, buf->data + off, copy_len);
        }

        // 释放缓冲区
        buf_release(buf);

        // 更新读取状态
        n += copy_len;
        off = 0; // 从第二个块开始，偏移量为0
    }

    return n; // 返回实际读取的字节数
}

// 写入 inode 管理的 data block (可能导致管理的 block 增加)
// 调用者需要持有 inode 锁
// 成功返回写入的字节数, 失败返回0
uint32 inode_write_data(inode_t* ip, uint32 offset, uint32 len, void* src, bool user)
{
    assert(sleeplock_holding(&ip->slk), "inode_write_data: lock not held");

    // 检查偏移量和长度是否合法
    if (offset > ip->size || offset + len < offset)
        panic("inode_write_data: invalid offset");
    if (offset + len > INODE_MAXSIZE)
        panic("inode_write_data: data exceeds maximum inode size");

    // 初始化变量
    uint32 bn = offset / BLOCK_SIZE; // 起始逻辑块号
    uint32 end_bn = (offset + len - 1) / BLOCK_SIZE; // 结束逻辑块号
    uint32 off = offset % BLOCK_SIZE; // 当前块内偏移量
    uint32 n = 0; // 已写入的字节数
    uint32 block_num;
    buf_t* buf;

    proc_t* p = myproc(); // 获取当前进程
    pgtbl_t user_pgtbl = p->pgtbl; // 获取用户页表

    // 遍历逻辑块
    for (; bn <= end_bn; bn++) {
        // 根据逻辑块号找到物理块号
        block_num = inode_locate_block(ip, bn);

        // 读取物理块
        buf = buf_read(block_num);

        // 计算本次写入长度
        uint32 copy_len = MIN(len - n, BLOCK_SIZE - off);

        // 数据拷贝：用户态或内核态
        if (user) {
            uvm_copyin(user_pgtbl, (uint64)(buf->data + off), (uint64)(src + n), copy_len);
        } else {
            memmove(buf->data + off, src + n, copy_len);
        }

        // 写回并释放缓冲区
        buf_write(buf);
        buf_release(buf);

        // 更新状态
        n += copy_len;
        off = 0; // 从第二个块开始，偏移量为 0
    }

    // 更新 inode 的大小并写回磁盘
    if (offset + n > ip->size) {
        ip->size = offset + n;
        inode_rw(ip, true);
    }

    return n; // 返回写入的总字节数
}

// 辅助 inode_free_data 做递归释放
static void data_free(uint32 block_num, uint32 level)
{  
    assert(block_num != 0, "data_free: block_num = 0");

    // block_num 是 data block
    if(level == 0) goto ret;

    // block_num 是 metadata block
    buf_t* buf = buf_read(block_num);
    for(uint32* addr = (uint32*)buf->data; addr < (uint32*)(buf->data + BLOCK_SIZE); addr++) 
    {
        if(*addr == 0) break;
        data_free(*addr, level - 1);
    }
    buf_release(buf);

ret:
    bitmap_free_block(block_num);
    return;
}

// 释放inode管理的 data block
// ip->addrs被清空 ip->size置0
// 调用者需要持有slk
void inode_free_data(inode_t* ip)
{
    assert(sleeplock_holding(&ip->slk), "inode_free_data: lock required");

    for (int i = 0; i < N_ADDRS_1; i++)
    {
        data_free(ip->addrs[i], 0);
        ip->addrs[i] = 0;
    }
    for (int i = N_ADDRS_1; i < N_ADDRS_1 + N_ADDRS_2; i++)
    {
        data_free(ip->addrs[i], 1);
        ip->addrs[i] = 0;
    }
    for (int i = N_ADDRS_1+N_ADDRS_2; i < N_ADDRS; i++)
    {
        data_free(ip->addrs[i], 2);
        ip->addrs[i] = 0;
    }

    // 更新 inode 的大小，表示数据已释放
    ip->size = 0;

    // 写回更新的 inode 到磁盘
    inode_rw(ip, true);
}


static char* inode_types[] = {
    "INODE_UNUSED",
    "INODE_DIR",
    "INODE_FILE",
    "INODE_DEVICE",
};

// 输出inode信息
// for dubug
void inode_print(inode_t* ip)
{
    assert(sleeplock_holding(&ip->slk), "inode_print: lk");

    printf("\ninode information:\n");
    printf("num = %d, ref = %d, valid = %d\n", ip->inode_num, ip->ref, ip->valid);
    printf("type = %s, major = %d, minor = %d, nlink = %d\n", inode_types[ip->type], ip->major, ip->minor, ip->nlink);
    printf("size = %d, addrs =", ip->size);
    for(int i = 0; i < N_ADDRS; i++)
        printf(" %d", ip->addrs[i]);
    printf("\n");
}